/**
 * LCR 123. 图书整理 I
 *
 *【简单】
 *
 * 书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。
 *
 * 示例 1：
 * 输入：head = [3,6,4,1]
 * 输出：[1,4,6,3]
 */

import { ListNode } from '../utils/list'

// 递归(利用函数调用栈)
// “递” 阶段先走至链表末尾
// head === null 为递归终止条件
// “归” 阶段依次将每个节点上的值加入列表，即可实现链表值的倒序输出
function reverseBookList(head: ListNode | null): number[] {
	return head === null
		? []
		: reverseBookList(head.next).concat(head.val as number)
}

// 栈
// 借助两个栈，先将链表中每个节点的值 push 进 stack1
// 然后再从 stack1 中 pop 出每个节点的值放入 stack2
function reversePrint(head: ListNode | null): number[] {
	const stack1: any[] = []
	const stack2: any[] = []
	while (head) {
		stack1.push(head.val)
		head = head.next
	}
	while (stack1.length) {
		stack2.push(stack1.pop())
	}

	return stack2
}
